146

12

Systems and Networks

Fig. 12.2 A fragment of a

network (graph). Note the

two types of nodes and that

some of the vertices are

directed

symmetric. An oriented graph is a directed graph in which every edge is oriented.

The element left bracket upper A Superscript r Baseline right bracket Subscript i j[A^r]i j gives the number of walks of length rr between nodes ii and j j. ¹⁰

If the only knowledge one has is of the positions of the objects in space, the

adjacency matrix can be constructed by defining an edge to exist between a pair of

objects if the distance between them is less than a certain threshold.

We begin by considering the structural properties of a network. Useful parameters

are the following:upper NN, the number of nodes;upper EE, the number of edges;left angle bracket k right angle bracket(k), the average

degree of each node (the number of other vertices to which a given vertex is joined);

upper LL, the network diameter (the smallest number of edges connecting a randomly

chosen pair of nodes; this is a global property); ¹¹ and the cliquishness German upper CC defined as

the fraction of nodes linked to a given vertex that are themselves connected (this is

a local property), or, in other words, the (average) number of times any two nodes

connected to the third node are themselves connected. Hence, this is equivalent to

the number of closed triangles in the network, that is,

German upper C proportional to trace upper A cubed commaC ∝Tr A³ ,

(12.13)

from which a relative clustering coefficient can be defined as

German upper C Subscript r Baseline equals German upper C divided by upper N periodCr = C/N .

(12.14)

The clustering coefficient upper CC of a node is defined as

upper C equals StartFraction 2 Delta Over k left parenthesis k minus 1 right parenthesis EndFractionC =

2Δ

k(k −1)

(12.15)

where DeltaΔ is the number of triangles in which a node is involved.

10 A mesh network is one in which there are at least two pathways of communication to each node.

Such networks are, of course, more resilient with respect to failure of some pathways.

11 A useful way to computeupper LL is given by Raine and Norris (2002).